#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

class NumberCombine:
    def __init__(self, target_num):
        self.num = target_num
        self.memory = {}            # dp的记忆体, 空间换时间, 递归中已经计算过的子问题做记录

        self.hit_memory_cnt = 0

    def partion_cnt(self):
        return self.partion_cnt_rec(self.num, 1)

    def partion_cnt_rec(self, num, min_begin):
        # 考虑对分割进行排序的情况, 按照最小值的情况递归处理
        # 返回值: 对num进行分割, 分割值中最小的数从min_begin开始的计数
        key = (num, min_begin)

        if num == 0:
            return 1

        if min_begin > num:
            return 0

        # if min_begin == num:
        #     return 1

        cnt = self.memory.get(key)
        if cnt is not None:
            self.hit_memory_cnt += 1
            return cnt

        cnt = 0
        for new_begin in range(min_begin, num):
            remain = num - new_begin
            if new_begin < min_begin:
                break

            cnt += self.partion_cnt_rec(remain, new_begin)

        # 以num作为min_begin的(在new_begin in range()中没有包括)
        cnt += 1

        self.memory[key] = cnt
        return cnt


def test():

    # from wiki: https://en.wikipedia.org/wiki/Partition_(number_theory)
    ans_lst = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604]

    for num, cnt in enumerate(ans_lst):
        # print(num, cnt)
        n = NumberCombine(num)
        assert n.partion_cnt() == cnt

    n = NumberCombine(50)
    assert n.partion_cnt() == 204226

    n = NumberCombine(120)
    assert n.partion_cnt() == 1844349560

    n = NumberCombine(130)
    # print( n.partion_cnt() )
    assert n.partion_cnt() == 5371315400

def main():
    print("start main")
    test()


if __name__ == "__main__":
    main()
